package com.adamjwh.pratice.offer;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 */
public class PermuteStr {

    ArrayList<String> list = new ArrayList<>();

    public ArrayList<String> Permutation(String str) {
        char[] chars = str.toCharArray();
        int len = chars.length;

        if(len == 0) {
            return list;
        }
        arrange(chars, 0, len);
        Collections.sort(list);

        return list;
    }

    private void arrange(char[] chars, int start, int len) {

        if(start == len-1) {
            if(! list.contains(String.valueOf(chars))) {
                list.add(String.valueOf(chars));
            }
            return;
        }

        for(int i=start; i<len; i++) {
            char temp = chars[i];
            chars[i] = chars[start];
            chars[start] = temp;

            arrange(chars, start+1, len);

            temp = chars[i];
            chars[i] = chars[start];
            chars[start] = temp;
        }
    }

}
